#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

 struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    
};
class Solution {
public:
    void reorderList(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr || head->next->next == nullptr) return;
        //�����м�ڵ�
        ListNode* slow = head, * fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        //����slow���м�ڵ�,����slow->Next�������һ���֣����������ˣ����������slow��һ����
        ListNode* newhead = new ListNode(0);
        ListNode* revslow = slow->next;
        //�ÿղ��ָܷ����������
        slow->next = nullptr;
        while (revslow)
        {
            ListNode* next = revslow->next;
            revslow->next = newhead->next;
            newhead->next = revslow;
            revslow = next;
        }
        //newhead->nextָ�������ĺ�벿��

        //�ϲ���������
        ListNode* nnewhead = new ListNode(0);
        ListNode* prev = nnewhead;
        //ListNode*l1 = head,*l2 = newhead->next;
        ListNode* l1 = head, * l2 = newhead->next, * next1 = l1->next, * next2 = l2->next;
        while (l1)
        {
            l1->next = l2;
            if (l2)
                l2->next = next1;
            ListNode* memnext1 = next1->next;
            if (next1)
                next1->next = next2;

            l1 = next1;
            l2 = next2;

            if (l2)
            {
                next2 = next2->next;
                next1 = memnext1;
            }
                


            // prev->next = l1;
            // l1 = l1->next;
            // prev = prev->next;
            // if(l2)
            // {
            //     prev->next = l2;
            //     l2 = l2->next;
            //     prev = prev->next;
            // }
        }

    }
};

int main()
{
   ListNode* head = new ListNode(1);
   ListNode* prev = head;
   prev->next = new ListNode(2);
   prev = prev->next;
   prev->next = new ListNode(3);
   prev = prev->next;
   prev->next = new ListNode(4);
   prev = prev->next;
   prev->next = new ListNode(5);
   Solution().reorderList(head);
}